package com.linzm.leetcode.mid.tree.其他;

/**
 * @Author zimingl
 * @Date 2023/2/24 23:40
 * @Description: 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
 * 二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
 * <p>
 * 输入：root = [3,4,5,1,2], subRoot = [4,1,2]
 * 输出：true
 * <p>
 * root 树上的节点数量范围是 [1, 2000]
 * subRoot 树上的节点数量范围是 [1, 1000]
 * -104 <= root.val <= 104
 * -104 <= subRoot.val <= 104
 */
public class Demo8IsSubtree572 {
    public static void main(String[] args) {
        TreeNode treeNode = searchBST(TreeNode.getTree(), 1);
        System.out.println(treeNode);
    }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        return outerDfs(root, subRoot);
    }

    // 双层递归
    public boolean outerDfs(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return false;
        }
        return innerDfs(root, subRoot) || outerDfs(root.left, subRoot) || outerDfs(root.right, subRoot);
    }

    private boolean innerDfs(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) {
            return true;
        }
        if (root == null || subRoot == null || root.val != subRoot.val) {
            return false;
        }
        return innerDfs(root.left, subRoot.left) && innerDfs(root.right, subRoot.right);
    }

    public static TreeNode searchBST(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        if (root.val == val) {
            return root;
        }
        return searchBST(val < root.val ? root.left : root.right, val);
    }
}
